Atualmente, estou escrevendo um analisador básico para um tipo de XML. Como exercício, estou implementando um analisador baseado em tabela LL. Este é meu exemplo de gramática BNF: % string de dados do nome do token %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: name attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" open_tag elem_or_data | data elem_or_data | / * epsilon * / ; attr: name ":" string attr | / * epsilon * / ; Esta gramática está correta? Cada terminal literal está entre aspas. Os terminais abstratos são especificados por% token. Estou codificando um lexer escrito à mão para converter minha entrada em uma lista de tokens. Como eu tokenizar os terminais abstratos?
2021-03-03 08:11:50
A abordagem clássica seria escrever uma expressão regular (ou outro reconhecedor) para cada terminal possível.
O que você chama de terminais "abstratos", que são perfeitamente concretos, são na verdade terminais cujos padrões associados reconhecem mais de uma string de entrada possível. A string realmente reconhecida (ou alguma função calculada dessa string) deve ser passada ao analisador como o valor semântico do token.
Nominalmente, em cada ponto da string de entrada, o tokeniser executará todos os reconhecedores e escolherá aquele com a correspondência mais longa. (Essa é a chamada regra de "mastigação máxima".) Geralmente, isso pode ser otimizado, principalmente se todos os padrões forem expressões regulares. (F) lex fará essa otimização para você, por exemplo.
Uma complicação no seu caso é que a tokenização do seu idioma depende do contexto. Em particular, quando o alvo é elem_or_data, as únicas possíveis símbolos são <,